#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

class Solution{
    public:
    int ans1(vector<vector<int>>& obstacleGrid){
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        if(n == 0){
            return 0;
        }
        vector<vector<int>> dp(m, vector<int>(n));
        if(obstacleGrid[0][0] == 1){
            dp[0][0] = 0;
        }else{
            dp[0][0] = 1;
        }
        for(int i = 0; i != m; i++){
            for(int j = 0; j != n; j++){
                if(obstacleGrid[i][j] == 1){
                    dp[i][j] = 0;
                }else{
                    if(i == 0 && j > 0){
                        dp[i][j] = dp[i][j-1];
                    }else if(j == 0 && i > 0){
                        dp[i][j] = dp[i-1][j];
                    }else if(i > 0 && j > 0){
                        dp[i][j] = dp[i-1][j] + dp[i][j-1];
                    }
                }
                
            }
        }

        return dp[m-1][n-1];
    }
};

void test(){
    Solution s;
    vector<vector<int>> obstacleGrid = {
        {0,0,0},
        {0,1,0},
        {0,0,0}
    };

    int ret = s.ans1(obstacleGrid);
    cout << ret << endl;
}

int main(void){
    test();

    return 0;
}